package com.tgy.leetcode;

import java.util.Arrays;

/**
 * @Author: tgy
 * @Date: 12/23/20 2:44 PM
 *
 *  https://leetcode-cn.com/problems/insertion-sort-list/
 */
public class _147_对链表进行插入排序_01 {

    public ListNode insertionSortList(ListNode head) {

        if (head == null) {

            return head;
        }

        ListNode dummy = new ListNode(Integer.MIN_VALUE);
        dummy.next = head;
        ListNode node = head;

        while (node.next != null) {

            // 这里要加等号，防止排序不稳定
            if (node.val <= node.next.val) {

                node = node.next;
                continue;
            }

            ListNode startNode = dummy;

            while (startNode.next.val <= node.next.val) {

                startNode = startNode.next;
            }

            ListNode tmpPre = startNode.next;
            startNode.next = node.next;
            ListNode tmpNext = node.next.next;
            node.next.next = tmpPre;
            node.next = tmpNext;
        }

        return dummy.next;
    }

    public static void main(String[] args) {

//        int  n = 10;
//
//        int m = ((n << 1)| 1);
//        System.out.println(m);

         // 0 异或任意一个数都等于 自身
//        n^0 == n;
//        n^n = 0;
        // 多个数异或根数的排序顺序无关

        test01();

    }

    public static void test01(){


//        int a = 10;
//        int b = 20;
//        int c = 30;
//
//        System.out.println((a ^ b ^ c) == (b ^ a ^ c));

        int a = 10;
        int b = 20;

        a = a^b;
        b = a^b;  // a^b^b = a^0 = a
        a = a^b; //  a^b^a = a^a^b = 0^b = b
    }



}
